Tên tuổi và sự nghiệp của Aleksandr Danilovich Menshikov gắn kết mật thiết với cuộc đời của Pyotr Đại đế, nhưng gốc gác của người phò tá nổi danh lại ẩn chìm trong huyền thoại. Vài người nói cha ông là nông dân người Litva, đã cho ông đi học nghề làm bánh ở Moskva. Họ kể rằng một ngày, ông đang đi dọc đường phố rao bán bánh ông làm thì Francis Lefort trông thấy ông, tỏ ra mến thích và đưa cậu bé vào làm gia nhân cho ông. Sau đó, dù thất học, nhờ tính nhanh nhẹn, tươi vui và dạn dĩ Menshikov thu hút sự chú ý của Sa hoàng. Ông được chuyển qua làm gia nhân cho Pyotr Đại đế. Với vị thế này, tuy chức vụ nhỏ nhưng nhờ được kề cận quân vương, Menshikov vận dụng khả năng làm mê hoặc lòng người và những mánh lới khác nhau để dần dà trở nên một trong những người giàu nhất và có quyền lực nhất châu Âu vào thế kỷ 18. Ông luôn tỏ ra liều lĩnh, đến mức biển thủ quá đáng số tiền được giao cho ông quản lý, và đến mức giúp ông ngăn chặn được cơn cuồng nộ của quân vương. Cuối cùng, Pyotr Đại đế đe dọa trả ông về đi bán bánh trên đường phố Moskva. Tối hôm ấy, Menshikov xuất hiện trước mặt Pyotr Đại đế mang tấm tạp dề và cầm một cái khay đựng bánh đeo qua vai, rao lên: "Bánh nóng! Bánh nóng! Bánh mới làm đây!" Pyotr Đại đế lắc đầu, phá lên cười và lại tha thứ cho ông.

Chuyện thực sự về ông có lẽ chỉ kém lý thú hơn một chút. Điều gần như chắc chắn là cha của Menshikov là binh sĩ phục vụ Sa hoàng Aleksei I rồi trở thành hạ sĩ văn phòng ở Preobrazhenskoe. Gốc gác của gia tộc có lẽ là Litva. Một nhà ngoại giao – người đã giúp Menshikov trở thành Hoàng thân của Thánh chế La Mã – tuyên bố rằng ông là hậu duệ của một gia đình quý tộc ngày xưa. Có lẽ các từ ngữ "quý tộc" và "ngày xưa" được thêm vào hầu Hoàng đế Hapsburg vốn bảo thủ cứng nhắc dễ chấp nhận ông hơn, nhưng có bằng chứng cho thấy thân nhân của Menshikov sinh sống ở Minsk, lúc ấy thuộc về Litva.